﻿// Learn more about F# at http://fsharp.net

// Learn more about F# at http://fsharp.net

module MaximumIndependentSetFinder=
    //Takes as parameters the current path, the colors of each vertex, and every vertex's spouse and returns whether or not it is an alternating path
    let IsAlternatingPath (path : int[]) (color : char []) (spouse : int [])=
        let mutable temp = true
        if color.[path.[0]]= 'W' && color.[path.[path.Length-1]]= 'W' then     
            for j in 0 .. path.Length/2-2 do
                if not(spouse.[path.[j*2+1]]=path.[j*2+2]) then
                   temp <- false
        else
            temp <- false
        temp
    //Adds to non-strings as String
    let plus x y = 
        let temp =  x.ToString() + y.ToString() 
        temp
    let plus2 x y = 
        let temp =  "[" + x.ToString()  + "]" + "[" + y.ToString()  + "]"
        temp
    //Checks if one array is contained in the other                    
    let contains x y =
    
        let temp1 = Array.fold (plus2) "" (x)
        let temp2 = Array.fold (plus) "" (y)
        if temp1.Contains (temp2) then
            true
        else
            false 
    let contains2 x y =
    
        let temp1 = Array.fold (plus2) "" (x)
        let temp2 = Array.fold (plus) "" (y)
        if temp1.Contains ("[" + temp2 + "]") then
            true
        else
            false 
    //A recursive method that checks if the given path is alternating and if so switches all the spouses and if not adds on one more vertex to the path and calls itself
    let rec allPaths (matches : int[][]) (path : int [])  (spouse : int []) (color : char [])= 
        if path.Length>1 && IsAlternatingPath path color spouse then
            for k in 0 .. path.Length/2 - 1 do
                                if spouse.[path.[2*k]]> - 1 then 
                                    spouse.[spouse.[path.[2*k]]]<- -1
                                if spouse.[path.[2*k+1]]> - 1 then 
                                    spouse.[spouse.[path.[2*k+1]]]<- -1
                                spouse.[path.[2*k]] <- path.[2*k+1]
                                spouse.[path.[2*k+1]] <- path.[2*k]
                                color.[path.[0]] <- 'G'
                                color.[path.[path.Length-1]] <- 'G'
           else
            for i in 0 .. matches.[path.[path.Length-1]].Length - 1 do
                if not (contains path [|matches.[path.[path.Length-1]].[i]|]) then
                    allPaths matches (Array.append path [|matches.[path.[path.Length-1]].[i]|]) spouse color
    
    //Takes an array of arrays where each array contained inside holds the location of every vertex that the given vertex is connected to, then returns the maximum matching set of all the spouses                                 
    let MaximumMatchingFinder (matches : int[][])=
        let spouse = [|for i in 0 .. matches.Length-1 -> -1|]
        let color = [|for i in 0 .. matches.Length-1 -> 'W'|]
        for i in 0 .. matches.Length-1 do
            if color.[i]='W' then
                let mutable path = [|i|]
                allPaths matches path spouse color 
        spouse

 //Takes an array of arrays where each array contained inside holds the location of every vertex that the given vertex is connected to, then returns the maximum independent set of vertices in the bipartite graph
    let MaximumIndependentFinder (matches : int[][])=
        let maxMatches = MaximumMatchingFinder matches
        let T = [|for i in 0 .. matches.Length-1 ->0|]
        for i in 0 .. matches.Length/2-1 do
            if matches.[i].Length = 0 then
                T.[i]<-1
        let IndependentInner i (T : int[]) (maxMatches : int[]) (matches : int [][])=
             for j in 0 .. matches.[i].Length-1 do
                    if  (i<matches.[i].[j]&& not(maxMatches.[i]=matches.[i].[j])) || (i>matches.[i].[j]&& (maxMatches.[i]=matches.[i].[j])) then
                            T.[matches.[i].[j]]<-1
                        
        for i in 0 .. T.Length-1 do 
            if T.[i]=1 then
                IndependentInner T.[i] T  maxMatches matches
               
        let mutable C = [||]    
        for i in 0 .. matches.Length-1 do
            if i<matches.Length/2-1 then
                if (T.[i]=0) then
                    C <- Array.append C [|i|]
            else
                if (T.[i]=1) then
                    C <- Array.append C [|i|]
        let mutable final = [||]
        for i in 0 .. matches.Length-1 do
            if not(contains2 C [|i|]) then
                final <- Array.append final [|i|]
        final
    (*
    let spouse =[|7; 6;-1;-1;-1;-1;1;0;-1;-1;-1;-1|]
    let color = [|'G';'G'; ' ';'W'; ' '; ' ';'G';'G';'W'; ' '; ' '; ' '|]
    let path = [|3;7;0;6;1;8;|]
    printfn "%b"(IsAlternatingPath path color spouse)

    *)
    //printfn "hi"
    //let test = [|[|6;7|];[|6;8|];[|9;10;11|];[|7|];[|6;9|];[|11|];[|0;1;4|];[|0;3|];[|1|];[|2;4|];[|2|];[|2;5|]|]
    //let test = [|[|5;6|];[|7|];[|4|];[||];[|2|];[|0|];[|0|];[|1|];|]
    //printfn "%A"(MaximumIndependentFinder test)
    
              
    